package com.buddy.learn.algorithm.letcode;

/**
 * @author Buddy
 * @date 2021/5/31
 */
public class _092反转链表区间2 {


    public static void main(String[] args) {

        ListNode head = initListNode();
        ListNode newHead = reverseBetween(head, 2, 4);
        ListNode root = newHead;
        while (root != null) {
            System.out.println(root.val);
            root = root.next;
        }

    }

    /**
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * <p>
     * 1 2 3 4 5
     * <p>
     * 1 3 2 4 5
     * <p>
     * 1 3 4 2 6
     *
     * @param head  单链表的头指针
     * @param left  left
     * @param right right
     * @return 反转后的链表
     */
    private static ListNode reverseBetween(ListNode head, int left, int right) {
        // 虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        // 初始化指针
        ListNode guard = dummyNode;
        ListNode point = dummyNode.next;

        // 将指针移动到相应的位置
        // guard 移动到第一个要反转的节点的前面
        // point 移动到第一个要反转的节点上
        for (int i = 0; i < left - 1; i++) {
            guard = guard.next;
            point = point.next;
        }

        // 头插法插入节点
        for (int i = 0; i < right - left; i++) {
            // 将 p 后面的删除
            ListNode removed = point.next;
            point.next = point.next.next;

            removed.next = guard.next;
            // 添加到 g 的后面
            guard.next = removed;
        }
        return dummyNode.next;


    }

    private static ListNode initListNode() {
        ListNode head = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        ListNode f = new ListNode(6);
        head.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;
        return head;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }
}
